import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。
 * 中序遍历（Morris）
 * https://leetcode.cn/problems/binary-tree-inorder-traversal/
 */
class InorderTraversalMorris {
    public List<Integer> inorderTraversal(TreeNode root) {
         List<Integer> ret=new ArrayList<>();
        TreeNode pre=null;
        while(root!=null){
            if(root.left!=null){
                pre=root.left;
                while(pre.right!=null&&pre.right!=root){
                    pre=pre.right;
                }
                if(pre.right==null){
                    pre.right=root;
                    root=root.left;
                }else{
                    pre.right=null;
                    ret.add(root.val);
                    root=root.right;
                }
            }else{
                ret.add(root.val);
                root=root.right;
            }
        }
        return ret;
    }
}